package unionFindStudy;

public class UnionFindStudy04 {

    /**
     * LeetCode T547 省份数量
     * 再写一遍并查集
     * @param args
     */
    public static void main(String[] args) {

    }

    public int findCircleNum(int[][] isConnected){
        int len = isConnected.length;
        //定义并查集
        UnionFind2 unionFind = new UnionFind2(len);
        //根据二维数组中的数值，对并查集进行更新
        for (int i = 0; i < len; i++){
            for (int j = 0; j < len; j++){
                if (isConnected[i][j] == 1){
                    unionFind.merge(i, j);
                }
            }
        }
        int setNum = unionFind.getSetNum();
        return setNum;

    }
}
//实现并查集
class UnionFind2{
    int[] parent;

    public UnionFind2(int n){
        parent = new int[n];
        for (int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    //实现合并 1-successfully 0-failed
    public int merge(int index1, int index2){
        int index1_root = find(index1);
        int index2_root = find(index2);
        if (index1_root == index2_root){
            //合并失败，集合中存在该节点
            return 0;
        } else {
            parent[index2_root] = index1_root;
            return 1;
        }
    }

    //实现查询算法
    public int find(int index){
        //查询过程中实现并查集的优化
        return parent[index]==index?index:(parent[index]=find(parent[index]));
    }
    //返回并查集中集合的数量
    public int getSetNum(){
        int count = 0;
        for (int i = 0; i < parent.length; i++){
            if (parent[i] == i){
                count++;
            }
        }
        return count;
    }
}
